#leetcode题目61：旋转链表
#难度：中等

#方法：链表

class ListNode:
    def __init__(self, data):
        self.val = data
        self.next = None

class LinkList:
    def __init__(self):
        self.head = None

    def initList(self, data):
        if not data:
            return None
        
        # 创建头结点
        self.head = ListNode(data[0])
        r = self.head
        p = self.head
        
        # 逐个为 data 内的数据创建结点,建立链表
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r

    def printlist(self, head):
        if head == None:
            return
        node = head
        while node != None:
            print(node.val, end=' ')
            node = node.next
        print()  # 换行

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not head.next:
            return head
        tail=head
        n=1
        while tail.next:
            tail=tail.next
            n+=1

        tail.next=head
        k=k%n
        for i in range(n-k):
            tail=tail.next

        head=tail.next
        tail.next=None

        return head


#测试数据
list_str=[1,2,3,4,5]
k=2
#预期输出：[4,5,1,2,3]
head=LinkList().initList(list_str)
solution=Solution()
LinkList().printlist(solution.rotateRight(head,k))

list_str=[0,1,2]
k=4
#预期输出：[2,0,1]
head=LinkList().initList(list_str)
solution=Solution()
LinkList().printlist(solution.rotateRight(head,k))


